package primary.code06_graph;

import java.util.*;

/**
 * @author Yudi Wang
 * @date 2021/7/16 17:04
 * <p>
 * 拓扑排序
 * <p>
 * 思路：节点的入度为依赖度，当一个节点已完成时，消除该节点的影响。
 * <p>
 * 初始化入度为0的队列
 * 初始化节点入度映射
 * while 队列不为空
 *      从入度0队列获取节点，加入到结果并消除其影响（对其他节点造成的入度）
 *      如果消除节点影响后，其他节点入度变为0则加入到队列
 * end
 * <p>
 * 工程应用：项目依赖编译
 */
public class Code04_TopologySort {

    /**
     * 修改了原数据结构，不推荐
     *
     * @param graph
     * @return
     */
    private static List<Node> TopologySort(Graph graph) {
        List<Node> res = new ArrayList<>();
        Queue<Node> notZero = new LinkedList<>();//入度不为0的节点
        Queue<Node> zero = new LinkedList<>();//入度为0的节点
        //初始化
        for (Node node : graph.nodes.values()) {
            if (node.in != 0) {
                notZero.add(node);
            } else {
                zero.add(node);
            }
        }
        while (!zero.isEmpty()) {
            Node node = zero.poll();
            res.add(node);
            for (Node next : node.next) {
                next.in--;
                if (next.in == 0) {
                    notZero.remove(next);
                    zero.add(next);
                }
            }
        }
        return res;
    }

    private static List<Node> TopologySortTest(Graph graph) {
        Map<Node, Integer> inMap = new HashMap<>();
        Queue<Node> zeroQueue = new LinkedList<>();
        for (Node node : graph.nodes.values()) {
            if (node.in == 0) {
                zeroQueue.offer(node);
            }
            inMap.put(node, node.in);
        }

        ArrayList<Node> res = new ArrayList<>();
        while (!zeroQueue.isEmpty()) {
            Node cur = zeroQueue.poll();
            res.add(cur);
            for (Node adjacentNode : cur.next) {
                Integer inPre = inMap.get(adjacentNode);
                Integer now = inPre - 1;
                if (now == 0) {
                    zeroQueue.offer(adjacentNode);
                }
                inMap.put(adjacentNode, now);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[][] arr = {
                {4, 1, 2},
                {3, 2, 3},
                {1, 1, 3},
                {1, 2, 4},
                {1, 4, 5},
                {1, 5, 3},
                {1, 3, 8}
        };
        Graph graph = GraphUtils.transferGraph(arr);
        //宽度优先遍历 1 2 4 5 3 8
        List<Node> listTest = TopologySortTest(graph);
        for (Node node : listTest) {
            System.out.println("   " + node.val);
        }
        System.out.println();
        //宽度优先遍历 1 2 4 5 3 8
        List<Node> list = TopologySort(graph);
        for (Node node : list) {
            System.out.println("   " + node.val);
        }
    }
}
